package 排序算法.冒泡排序;

import java.util.Arrays;

/**
 * @Project: Data Structure and Algorithms
 * @Package: 排序.冒泡排序
 * @ClassName: BubbleSort01
 * @Author: zhouyihe
 * @Date: 2025/11/4 22:48
 * @Description: 冒泡排序 排序优化 鸡尾酒排序(双向冒泡排序)
 */
public class BubbleSort {

    /**
     * 冒泡排序
     * 优点:
     * 代码简单，容易实现,
     * 适合小规模数据排序
     * 对于几乎已经排好序的数据，效率较高
     * 稳定的排序算法
     * 缺点:
     * 时间复杂度: O(n^2)
     * 随着元素数量增加，效率急剧下降
     * 每次只能将一个元素移动到其最终位置，效率不高
     * @param arr1
     */
    private static void bubbleSort(int[] arr1) {
        for (int i = 0; i < arr1.length - 1; i++) {
            for (int j = 0; j < arr1.length - 1 - i; j++) {
                if (arr1[j] > arr1[j + 1]) {
                    int temp = arr1[j];
                    arr1[j] = arr1[j + 1];
                    arr1[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 冒泡排序优化
     * 如果是一个已经排好序的数组，上述代码也会循环执行，我们可以针对这一点进行如下优化：
     * 优化：提前结束冒泡
     * @param arr2
     */
    private static void optimizedBubbleSort(int[] arr2) {
        boolean swapped;
        for (int i = 0; i < arr2.length - 1; i++) {
            swapped = false;
            for (int j = 0; j < arr2.length - 1 - i; j++) {
                if (arr2[j] > arr2[j + 1]) {
                    int temp = arr2[j];
                    arr2[j] = arr2[j + 1];
                    arr2[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果没有发生交换，说明数组已经有序，可以提前退出排序
            if (!swapped) {
                break;
            }
        }
    }

    /**
     * 鸡尾酒排序(双向冒泡排序)
     * @param arr
     */
    public static void cocktailSort(int[] arr) {
        boolean swapped = true;
        int start = 0;
        int end = arr.length - 1;

        while (swapped){
            // 从左到右
            swapped = false;
            for (int i = start; i < end; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    swapped = true;
                }
            }

            // 如果没有交换,则表示排序完成了,提前结束
            if (!swapped) break;

            // 否则重置swapped标志准备从右到左
            swapped = false;
            end--;

            // 从右到左
            for (int i = end - 1; i >= start; i--) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    swapped = true;
                }
            }

            start++;
        }
    }

    //计数器和测试法
    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            cocktailSort(arr1);
            Arrays.sort(arr2);
            if (!isEqual(arr1, arr2)) {
                System.out.println("出错了！");
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println("测试结束");
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
